using System;
using System.Linq;
using NUnit.Framework;

namespace Solver
{
	/// <summary>
	/// What is the value of the first triangle number to have over five hundred divisors?
	/// </summary>
	public class Problem012 : SelfChecker, IProblem
	{
		private static readonly EratosthenesSieve PrimesSource = new EratosthenesSieve(65000);

		public int Id
		{
			get { return 12; }
		}

		public string Solve()
		{
			return Solve(500).ToString();
		}

		[Test]
		public override void Check()
		{
			Assert.AreEqual(28, Solve(5));
			Assert.AreEqual(36, Solve(8));
			Assert.AreEqual(76576500, Solve(500));
		}

		private static long Solve(int param)
		{
			int prevOmega = 1;
			for (int n = 3; ; n++)
			{
				var omega = n % 2 == 0 ? CountDivisors(n / 2) : CountDivisors(n);
				if (omega * prevOmega > param)
					return n * (n - 1) / 2;
				prevOmega = omega;
			}
		}

		private static int CountDivisors(long n)
		{
			int lastIndex = 0;
			var powers = new int[100];
			foreach (var p in PrimesSource.Primes())
			{
				while (n % p == 0)
				{
					powers[lastIndex]++;
					n /= p;
				}
				++lastIndex;
				if (n == 1) break;
				if (lastIndex >= powers.Length)
					Array.Resize(ref powers, powers.Length * 2);
			}
			Assert.AreEqual(1, n);
			return powers.Take(lastIndex).Aggregate(1, (omega, p) => omega * (p + 1));
		}
	}
}